Search for: All records

Let (kn)n∈N be a sequence of positive integers growing to infinity at a sublinear rate, kn → ∞ and kn/n → 0 as n → ∞. Given a sequence of n-dimensional random vectors {Y (n)}n∈N belonging to a certain class, which includes uniform distributions on suitably scaled ℓnp -balls or ℓnp -spheres, p ≥ 2, and product distributions with sub-Gaussian marginals, we study the large deviations behavior of the corresponding sequence of kn-dimensional orthogonal projections. For almost every sequence of projection matrices, we establish a large deviation principle (LDP) for the corresponding sequence of projections, with a fairly explicit rate function that does not depend on the sequence of projection matrices. As corollaries, we also obtain quenched LDPs for sequences of ℓ2-norms and ℓ∞-norms of the coordinates of the projections. Past work on LDPs for projections with growing dimension has mainly focused on the annealed setting, where one also averages over the random projection matrix, chosen from the Haar measure, in which case the coordinates of the projection are exchangeable. The quenched setting lacks such symmetry properties, and gives rise to significant new challenges in the setting of growing projection dimension. Along the way, we establish new Gaussian approximation results on the Stiefel manifold that may be of independent interest. Such LDPs are of relevance in asymptotic convex geometry, statistical physics and high-dimensional statistics. 

Randomized load-balancing algorithms play an important role in improving performance in large-scale networks at relatively low computational cost. A common model of such a system is a network of N parallel queues in which incoming jobs with independent and identically distributed service times are routed on arrival using the join-the-shortest-of-d-queues routing algorithm. Under fairly general conditions, it was shown by Aghajani and Ramanan that as the size of the system goes to infinity, the state dynamics converge to the unique solution of a countable system of coupled deterministic measure-valued equations called the hydrodynamic equations. In this article, a characterization of invariant states of these hydrodynamic equations is obtained and, when d=2, used to construct a numerical algorithm to compute the queue length distribution and mean virtual waiting time in the invariant state. Additionally, it is also shown that under a suitable tail condition on the service distribution, the queue length distribution of the invariant state exhibits a doubly exponential tail decay, thus demonstrating a vast improvement in performance over the case [Formula: see text], which corresponds to random routing, when the tail decay could even be polynomial. Furthermore, numerical evidence is provided to support the conjecture that the invariant state is the limit of the steady-state distributions of the N-server models. The proof methodology, which entails analysis of a coupled system of measure-valued equations, can potentially be applied to other many-server systems with general service distributions, where measure-valued representations are useful. 

Consider an interacting particle system indexed by the vertices of a (possibly random) locally finite graph whose vertices and edges are equipped with weights or marks that represent parameters of the model, such as the environment and initial conditions. Each particle takes values in a countable state space and evolves according to a pure jump process whose jump rates depend only on its own state (or history) and marks, and states (or histories) and marks of particles and edges in its neighborhood. Under mild conditions on the jump rates, it is shown that if the sequence of (marked) interaction graphs converges in probability in the local weak sense to a limit (marked) graph that satisfies a certain finite dissociability property, then the corresponding sequence of empirical measures of the particle trajectories converges weakly to the law of the marginal dynamics at the root vertex of the limit graph. The proof of this hydrodynamic limit relies on several auxiliary results of potentially independent interest. First, such interacting particle systems are shown to be well-posed on (almost surely) finitely dissociable graphs, which include graphs with uniformly bounded maximum degrees and any Galton-Watson tree whose offspring distribution has a finite first moment. A counterexample is also provided to show that well-posedness can fail for dynamics on graphs outside this class. Next, given any sequence of graphs that converges in the local weak sense to a finitely dissociable graph, it is shown that the corresponding sequence of jump processes also converges in the same sense to a jump process on the limit graph. Finally, the dynamics are also shown to exhibit an (annealed) asymptotic correlation decay property. These results complement recent work on hydrodynamic limits of locally interacting probabilistic cellular automata and diffusions on sparse random graphs. However, the analysis of jump processes requires very different techniques, including percolation arguments and notions such as consistent spatial localization and causal chains. 

Accurate estimation of tail probabilities of projections of high-dimensional probability measures is of relevance in high-dimensional statistics and asymptotic geometric analysis. Whereas large deviation principles identify the asymptotic exponential decay rate of probabilities, sharp large deviation estimates also provide the “prefactor” in front of the exponentially decaying term. For fixed p ∈ (1, ∞), consider independent sequences (X(n,p))_{n∈N} and (Θ_n)_{n∈N} of random vectors with Θn distributed according to the normalized cone measure on the unit l^n_2 sphere, and X(n,p) distributed according to the normalized cone measure on the unit lnp sphere. For almost every realization (θn)_{n∈N} of (Θ_n)_{n∈N}, (quenched) sharp large deviation estimates are established for suitably normalized (scalar) projections of X(n,p) onto θ_n, that are asymptotically exact (as the dimension n tends to infinity). Furthermore, the case when (X(n,p))_{n∈N} is replaced with (X(n,p))_{n∈N}, where X(n,p) is distributed according to the uniform (or normalized volume) measure on the unit lnp ball, is also considered. In both cases, in contrast to the (quenched) large deviation rate function, the prefactor exhibits a dependence on the projection directions (θ_n)_{n∈N} that encodes additional geometric information that enables one to distinguish between projections of balls and spheres. Moreover, comparison with numerical estimates obtained by direct computation and importance sampling shows that the obtained analytical expressions for tail probabilities provide good approximations even for moderate values of n. The results on the one hand provide more accurate quantitative estimates of tail probabilities of random projections of \ell^n_p spheres than logarithmic asymptotics, and on the other hand, generalize classical sharp large deviation estimates in the spirit of Bahadur and Ranga Rao to a geometric setting. The proofs combine Fourier analytic and probabilistic techniques. Along the way, several results of independent interest are obtained including a simpler representation for the quenched large deviation rate function that shows that it is strictly convex, a central limit theorem for random projections under a certain family of tilted measures, and multidimensional generalized Laplace asymptotics. 

Consider a system of homogeneous interacting diffusive particles labeled by the nodes of a unimodular Galton–Watson tree, where the state of each node evolves infinitesi- mally like a d-dimensional diffusion whose drift coefficient depends on (the histories of) its own state and the states of neighboring nodes, and whose diffusion coefficient depends only on (the history of) its own state. Under suitable regularity assumptions on the coefficients, an autonomous characterization is obtained for the marginal dis- tribution of the dynamics of the neighborhood of a typical node in terms of a certain local equation, which is a new kind of stochastic differential equation that is nonlinear in the sense of McKean. This equation describes a finite-dimensional non-Markovian stochastic process whose infinitesimal evolution at any time depends not only on the structure and current state of the neighborhood, but also on the conditional law of the current state given the past of the states of neighborhing nodes until that time. Such marginal distributions are of interest because they arise as weak limits of both marginal distributions and empirical measures of interacting diffusions on many sequences of sparse random graphs, including the configuration model and Erdös–Rényi graphs whose average degrees converge to a finite non-zero limit. The results obtained complement classical results in the mean-field regime, which characterize the limiting dynamics of homogeneous interacting diffusions on complete graphs, as the num- ber of nodes goes to infinity, in terms of a corresponding nonlinear Markov process. However, in the sparse graph setting, the topology of the graph strongly influences the dynamics, and the analysis requires a completely different approach. The proofs of existence and uniqueness of the local equation rely on delicate new conditional independence and symmetry properties of particle trajectories on unimodular Galton– Watson trees, as well as judicious use of changes of measure. 

Let (ak)k∈N be an increasing sequence of positive integers satisfying the Hadamard gap condition a_{k+1}/a_k > q > 1 for all k ∈ N, and let S_n(ω) = \sum_{k=1}^n cos(2πa_kω), n ∈ N, ω ∈ [0, 1]. Then S_n is called a lacunary trigonometric sum, and can be viewed as a random variable defined on the probability space Ω = [0, 1] endowed with Lebesgue measure. Lacunary sums are known to exhibit several properties that are typical for sums of independent random variables. For example, a central limit theorem for (S_n)_{n∈N} has been obtained by Salem and Zygmund, while a law of the iterated logarithm is due to Erdős and Gál. In this paper we study large deviation principles for lacunary sums. Specifically, under the large gap condition ak+1/ak → ∞, we prove that the sequence (Sn/n)n∈N does indeed satisfy a large deviation principle with speed n and the same rate function I􏰡 as for sums of independent random variables with the arcsine distribution. On the other hand, we show that the large deviation principle may fail to hold when we only assume the Hadamard gap condition. However, we show that in the special case when ak = qk for some q ∈ {2, 3, . . .}, (S_n/n)_{n∈N} satisfies a large deviation principle (with speed n) and a rate function I_q that is different from I, and describe an algorithm to compute an arbitrary number of terms in the Taylor expansion of Iq . In addition, we also prove that Iq converges pointwise to I as q → ∞. Furthermore, we construct a random perturbation (a_k)_{k∈N} of the sequence (2^k)_{k∈N} for which a_{k+1}/a_k → 2 as k → ∞, but for which at the same time (S_n/n)n∈N satisfies a large deviation principle with the same rate function I as in the independent case, which is surprisingly different from the rate function I_2 one might naïvely expect. We relate this fact to the number of solutions of certain Diophantine equations. Together, these results show that large deviation principles for lacunary trigonometric sums are very sensitive to the arithmetic properties of the sequence (a_k)_{k∈N}. This is particularly noteworthy since no such arithmetic effects are visible in the central limit theorem or in the law of the iterated logarithm for lacunary trigonometric sums. Our proofs use a combination of tools from probability theory, harmonic analysis, and dynamical systems.